package leetcode.动态规划.simple;

/**
 * @author wangmaolin1
 * @date 2022/1/16 上午10:14
 */
public class _1646获取生成数组中的最大值 {

    /**
     * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
     * <p>
     * nums[0] = 0
     * <p>
     * nums[1] = 1
     * <p>
     * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
     * <p>
     * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1] 返回生成数组 nums 中的 最大 值。
     * <p>
     * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/get-maximum-in-generated-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param n
     * @return
     */
    public int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;

        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        int max = 0;
        for (int i = 0; (2 * i) <= n; i++) {
            dp[2 * i] = dp[i];
            max = Math.max(max, dp[2 * i]);
            if (2 * i + 1 <= n) {
                dp[2 * i + 1] = dp[i] + dp[i + 1];
                max = Math.max(max, dp[2 * i + 1]);
            }

        }
        return max;

    }

}
